2023 祥云杯决赛

Van1sh 比赛小屋 Write Up

创建时间:2023-09-21 11:47

字数:2.5k 阅读:

学生组
1. 赛题一
2. 赛题二
社会组

虽然本人没有参加第三届祥云杯决赛，但赛后还是摸到了赛题看。

学生组

有一个师傅在学生组，第一天学生组比完CTF后找到我说，在比赛的时候解题卡在了最后一步，让我瞅瞅，想知道怎么做。

赛题一

from secret import flag
from Crypto.Util.number import *
total_bit = 512
def make_para(bit_size):
    P = getStrongPrime(bit_size)
    Q = getStrongPrime(bit_size)
    N = P * Q
    magic = (N + 1) * (N + P + Q + 1) + (P - Q) ** 2 + N
    d = int(0.394 * bit_size)
    e = inverse(d, magic)
    k = d * e // magic
    return (N, e), (P, Q, k)
pubkey, sec_key = make_para(2 * total_bit)
flag = bytes_to_long(flag) * sec_key[2]
p = getStrongPrime(total_bit)
q = getStrongPrime(total_bit)
n = p * q
e = 65537
c = pow(flag, e, n)
t = ((p - getRandomNBitInteger(16)) * sec_key[0] + q) % sec_key[1]
with open('output.txt', 'w') as f:
    f.write(str(pubkey) + '\n')
    f.write(str((t, c)))

题目大致的瞅一眼，首先生成了一些参数 $N,e,(P,Q,k)$ 其中 $N,e$ 已知。然后把 flag 乘了 k，接着又生成了一份 RSA 的公钥，并加密了 $k \cdot flag$ ，然后给出了关于 $p,q$ 的额外信息 $t = ((p-random) * P + q) % Q$

那么问题很显然啊，需要先分解 $N$，把 $P,Q,k$ 整出来先。而关于 $P,Q$，在 make_para 函数中我们注意到关于 $e,d$ 的生成方式。乍一看，还以为生成了一个大小是 $N^{0.394}$ 的私钥，然后用来生成 $e$ 的模数是 magic，合并一下其实是 $(P^2+P+1)(Q^2+Q+1)$，还以为是论文题，要用一下连分数啥的。但是转念一想，不对啊，离线比赛出论文题，那不是缺了大德么。最后定睛一看，好家伙 d = int(0.394 * bit_size)，原来 $d$ 是一个已知整数。

于是我们有 $e \cdot d = k (P^2+P+1)(Q^2+Q+1)+1$，展开一下 $e\cdot d-1 = k(N^2+PN+QN+P^2+Q^2+N+P+Q+1)$

因此 $\lfloor \frac{e\cdot d-1}{N^2}\rfloor = k$，假设 $P>Q$，那么 $Q^2 \lt N \lt P^2$，于是 $\lfloor \frac{e\cdot d-1}{kN}\rfloor \approx N +P+Q+2$，实际测出来是 $\lfloor \frac{e\cdot d-1}{kN}\rfloor = N +P+Q+3$

然后解个方程我们就能获取 $P,Q,k$ 了。

from gmpy2 import *

N,e = (21136120517038375343657055317361461947217610380415290931285704769845405139443342030139838613845989765254932385503454684656325859309861269837188207923942223163348944160792729101485975484543693998035828762630825174735962679103457025646672449491007685400869138263581883506767852264244013623583813540066115060793144049256890248337903932112449333735324371400873419104520104079223733159263094092843185909770131443506433825708789563521497940390674504488024226655482568491358458107989880756229607524452273305978138461190013290440068226454238375505010225133919526068226837545142734502100757510899741312502285931571783851666429, 291542085122413541028076006933740091355832744332602513957292369860771664833892358795585946753279254101863581542678927529330607906769804928526978686071141386341893467977451552634615917127445748737712286687041822255325772392569586666055711202824870471562051621883329559663555059967665101455578668904247279540014709971958403913939101728330638301270881265277488332145439522278871554725936095617940701105161078332467466405454007283937177070102098256744642045839067405705972784471374421818844770106228499198315920181837950503279178647052157269318876892192700670366858062171759498850112906238502375693099462427930964555274451795362167393410749436026095037695100430810204847979914959732383773952788768239221142673268839750770222737928397507645337714199166919835667638401309062163501094032890215821366318775462220119081175885338966308921205861717088926659072208866126879068213582499260316364548817213314952246293713853884872460934174624844462586276340207505217646013915381902979372875919823493439285174120160656952728493383464761519634974414670811896809158801804891938928244053980210687334268664219571818927285279999791212932795196689285015367417706597781418431735001428656415752334850685705212368666855124013583549768407830008606258798409140)
d = int(0.394 * 1024)

k = (e*d-1)//N**2
p_a_q = (e*d-1)//(k*N) - N - 3
p_s_q = iroot(p_a_q**2-4*N,2)[0]
p = (p_a_q+p_s_q)//2
q = p_a_q - p
assert p*q == N

print(p)
print(q)
print(k)

# 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
# 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 263

显然我们是需要根据 $t = ((p-random) * P + q) % Q$ 解出 $p,q$ 来解密密文获得 flag

这里由于 $P,Q$ 是 1024 比特的，$p,q$ 是 512 比特。考虑格基规约，类似的，构造如下格

from Crypto.Util.number import *
p = getPrime(510)
q = getPrime(510)
n = p * q
t = ((p - getRandomNBitInteger(16)) * P + q) % Q
shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
				[shift*1,0,1,0,0],
				[shift*Q,0,0,1,0],
				[shift*t,0,0,0,2^512]])
m = m.LLL()

assert abs(m[1][2])==q

本地测试发现当 $p,q$ 长度为 $510$ 的时候能跑出来，但是使用原来数据时，$p,q$ 多 2 个比特就怎么也出不来。

于是想到爆破 $p,q$ 的高位，首先最高位肯定都是 1，对于第二个比特，猜一下，总共也就四种可能。（另外 $P,Q$ 也有可能会反，需要对调一下，总共就是 8 种可能）

t,c = (18872151984199200051633005759140295224788252451326410141022483203855894790958837408470348915966212063467995292461061069273539234939320647533902914083943444743748789975745514239518406829738286900177972974033143896932863898553599888597165054837513698667686277110587659188172271629973371164557353473146831275972, 47672712219012743425382676880904671136942826695249149129159924785186563239747047304204962529935078111450524236186612259355850306867579998685662967391936502046679744616903469002187225791339629835786750259999982506494377133775859573660632942293353420327987860136624649402598383416748766985203781387716072244402)
k = 263
P = 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591
Q = 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219
# 猜测 p,q 高位
ph = 0b11<<510
qh = 0b11<<510

# 根据 p,q 高位， t 做相应处理
tbar = (t-qh-ph*P)%Q

shift = 2^1024
m = matrix(ZZ,[[shift*P,1,0,0,0],
				[shift*1,0,1,0,0],
				[shift*Q,0,0,1,0],
				[shift*tbar,0,0,0,2^512]])
m = m.LLL()

if isPrime(int(abs(m[1][2])+qh)):
	q = abs(m[1][2])+qh
	e = 65537
	d = inverse(e,q-1)
	mm = pow(c,d,q)
	print(long_to_bytes(int(mm//k)))

b'flag{6db64079-711c-4d80-86c6-baec1023d44d}'

赛题二

然后我把第二题给问过来了，

from Crypto.Util.number import *
from Crypto.Util.strxor import strxor
from random import randint
from gmpy2 import invert
import os

flag = b'xxx'

def mypad(m):
    l = len(m)
    r = 190 - l
    padded_m = m + os.urandom(r)
    return padded_m

def myfunction(num):
    output = 0
    j = 0
    for i in range(num):
        output += (i+j)*6 + 1
        j += i
    return output

def mix(a,b):
    return a | b , a * b


class MySeries():
    def __init__(self, num):
        self.num = num

    def Coe(self, n):
        i = 0
        c = 1
        while i < n:
            i += 1
            c = (c * (1 / 2 - i + 1)) / i
        return c

    def Point(self, center):
        sum = 0
        center -= 1
        i = 0
        while i < self.num:
            sum += (center ** (1 / 2 - i) * self.Coe(i))
            i += 1
        return sum


def All(bound):
    num = randint(1111, 2222)
    T = MySeries(num)
    output = 0

    i = 3
    while i < bound:
        b1 = T.Point(i)
        b2 = T.Point(i + 1)
        output += (b1 + b2) / 2
        i += 1
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p,q = getPrime(512),getPrime(512)
    
    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break
            
    n = p * q * r 
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1,p % (2 ** 400),mod)
    k = int(All(n))
    xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag)
    pad_flag = mypad(xor_flag)
    m = bytes_to_long(pad_flag)
    c = pow(m,65537,n)
    
    print('All data:')
    print(f'flag_len = {flag_len}')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')

'''
All data:
flag_len = 42
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471
c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960
hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949
hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366
'''

赛题二就比较缝合怪了，魔改的应该是 2022 CCTF Infinity castle

第一步是用 $hint1$ 和 $n$ 做 gcd 求出 $r$，

然后测试（或者推一下）可得 myfuction 其实就是一个计算三次方的函数，

于是，根据二项式定理，我们可以利用 $hint2$ 求出 $p %400 = \frac{hint %400}{3n}$ ，

有了 $p$ 的低 400 位，来一个 copper 就能分解 $n$ 了。

最后为了解密 flag 还得求出 $k$，这个 All 函数其实就是一个泰勒展开在求 $\sqrt{n}$ 的积分，所以 $k = \frac{2}{3}n^\frac{3}{2}$


    n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471

    r = 13064264216014600984590013161094647588688097945008015283029781423081403612570218487688473281971441574006356719607329041516297420593832435695152551495621303

    # n = p * q * r 
    # mod = myfunction(3)
    # print(mod==n**3)

    # hint2 = pow(3*n+1,p % (2 ** 400),n**3)
    # hint2 = pow(3*n+1,400,n**3)
    # print((hint2%(n**2))//n)
    # pbar = (hint2%(n**2))//(3*n)
    # # pbar = 290093818088445232385211155295987419950746202522777816778903667287369882202987169000686051435796089920601608052312746065
    # R.<x> = Zmod(n)[]
    # f = (2^400) * x + pbar
    # x0 = f.monic().small_roots(X=2^112,beta=0.49)[0]
    # p = int(f(x0))
    # q = int(n)//p
    # p = 10835491201779459536146517032534966141751744767433086585469873899474443209697998673019277269625767885233333299822821960132722036029334072360300733477529681
    # q = 13316873218544878416280346742338579649540959399378233738197413050519025036683226049252858246940675299712559597339200613975360145818807371576573913305896497
    # phi = (p-1)*(q-1)*(r-1)
    # d = inverse(e,phi)
    # m = pow(c,d,p*q*r)
    # m = long_to_bytes(m)
    # 
    


    k = 2*(n*iroot(n,2)[0])//3
    xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag[:42])
    xor_flag

b'flag{84934a62-f932-968c-fa88-22f0284c0e8e}'

社会组

同事在社会组的 SU，赛后也把题目给我瞅了瞅，于是在去陇剑杯的飞机上看了一下

from secret import flag, genPrime, generate_g
import random
import math
import os

sieve_base = # from Crypto.Util.number import sieve_base

def rabinMillerTest(n, rounds):
    tested = []
    if n < 3 or (n & 1) == 0:
        return n == 2, tested
        # n might be very large so it might be beneficial to precalculate n-1
    n_1 = n - 1
    # determine m and b so that 2**b * m = n - 1 and b maximal
    b = 0
    m = n_1
    while (m & 1) == 0:
        b += 1
        m >>= 1
    #a smaller number might be faster...
    upper = 2**(max(n.bit_length() >> 5, 10))
    # we need to do at most n-2 rounds.
    for i in range(min(rounds, n - 2)):
        a = random.randint(2, upper)
        while a in tested:
            a = random.randint(2, upper)
        tested.append(a)
        # do the rabin-miller test
        z = pow(a, m, n)  # (a**m) % n
        if z == 1 or z == n_1:
            continue
        composite = 1
        for r in range(b):
            z = (z * z) % n
            if z == 1:
                return 0, tested
            elif z == n_1:
                composite = 0
                break
        if composite:
            return 0, tested
    return 1, tested

def is_prime(N, false_positive_prob=1e-6):
    tested = []
    if N < 3 or N & 1 == 0:
        return N == 2, []
    for p in sieve_base:
        if N == p:
            return 1, tested
        if N % p == 0:
            tested.append(p)
            return 0, tested

    rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))
    return rabinMillerTest(N, rounds)

print("Welcome to my secure key exchange system\n")
while True:
    q = int(input("q:"))
    if q.bit_length() < 256:
        print("oh! too small!!!")
        continue
    jud, tested = is_prime(q)
    if not jud:
        print(f"Bad parameters! test set {tested} not pass.")
    else:
        break

x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big')
p = genPrime(q)
g = generate_g(q, p)
print(f"p: {p}")
print(f"g: {g}")
A = pow(g, x, p)
print(f"Calculate the public key in this way: pow(g, secret, p)")
print(f"eg. pow(g, x, p) = {A}")
print(f"I can give you a hint:)")
r = int(input("r:"))
if r < x and ((p - 1) % r == 0):
    print(pow(g, x, r))
else:
    print("don't need hint?")

for i in range(100):
    B = int(input("give me your public key:"))
    if 1 < B < p:
        shared = pow(B, x, p)
        print(f"our shared key: {shared}")
        x_ = int(input("x?").strip())
        if x_ == x:
            print(flag)
        else:
            print("sorry~")

是一个需要交互的题，把函数 genPrime, generate_g 给偷摸隐藏了起来，估计是有点问题。看一下题目流程：

用户端输入一个大于 256 比特的素数 $q$
服务端随机生成一个秘密数 $x$，并根据用户的 $q$ 生成一个素数 $p$，在根据 $p,q$ 生成一个 $g$，并给出 $A \equiv g^x \pmod p$。（由于没有源码，这里合理猜测生成的 $p-1$ 具有因子 $q$，而 $g$ 是一个在模 $p$ 阶为 $q$ 的一个元素，这是 Elgamal 参数生成的标准）
服务端允许用户输入一个 $r$，如果满足 $r \lt x,p-1 \equiv 0 \pmod r$，服务端就会输出 $g^x %r$
之后服务端让用户输入一个 $B$，并给出 $B^x \pmod p$（就是一个 ECDH），然后让用户猜 $x$，猜对了就给 $flag$，一共一百次交互机会。

乍一看给出了 rabinMillerTest 还以为让绕过素数检测，但根据后面的流程来看，估计预期应该是根据 hint 得到一些关于 $x$ 信息，再利用一百次交互，每次搞到一点额外的信息，最后恢复完整的 $x$ 叭。

但是，注意到给 hint 的部分会给出 $g^x %r$，因此，只要 $r-1$ 是光滑的，就能解出 $x$ 了。而 $r$ 得是 $p-1$ 的一个因子，如果我们对 genPrime 函数猜测的正确的话，那就直接设 $r$ 为 $q$，而 $q-1$ 是一个光滑数就行了。至于和 $x$ 的大小关系，由于 $x$ 的生成和 $q$ 的比特有关 x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big') ，注意这里 $x$ 并不是严格小于 $q$，所以爆！为了消去“地板除”的影响，要找比特长度刚好是 8 的倍数的 $q$，然后多跑几次等 $x$ 比 $r$ 大，我们就可以直接解 $DLP$ 得到 $x %r$，然后根据大小关系，对结果加一个 $r$ 就是 $x$ 了。

生成 $p-1$ 光滑的素数 $p$ 的脚本

from Crypto.Util.number import *
import random

def genPrime(bit_len):
	while True:
		x = 2
		while x < 2**bit_len:
			x *= random.choice(sieve_base)
		if isPrime(x+1) and x.bit_length() % 8 == 0:
			return x+1
print(genPrime(256))

（不过由于没有赛题源码，以上想法全是基于猜测正确的前提下）

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 643713081@qq.com